package com.algorithm3;

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int[] array,int p,int r) {
        if(p>=r){
            return;
        }
        int pivot =partion(array,p,r);
        quickSort(array,p,pivot-1);
        quickSort(array,pivot+1,r);
    }

    public static int partion(int[] array,int p,int r){
        int pivot = r;
        //i分隔了数据，i前面为已处理数组，i之后为未处理数组
        int i = p;//假设i位置的数比pivot位置的数大，往后寻找比array[pivot]小的数，交换，再重新规划i的位置
        //j表示未处理部分，有符合的一个j，就将j加到i末尾
        //i用于指示比array[pivot]大的数据,j用于指示比array[pivot]小的数据，
        // 比对结果即是将array[j]放到array[i]的后边，用swap即可
        for(int j=p;j<r;j++){
            if(array[j]<array[pivot]){
                swap(array,i,j);
                i++;
            }
        }
        swap(array,i,r);
        System.out.println("排序中:"+"i="+i+"-->"+ Arrays.toString(array));
        return i;
    }
    public static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args){
        int[] array = new int[]{5,7,6,8,9,3,2,4,1,10};
        System.out.println("排序前:"+ Arrays.toString(array));
        quickSort(array,0,array.length-1);
        System.out.println("排序后:"+ Arrays.toString(array));
    }
}
